//
// Created by Incredible on 17/3/22.
//

#ifndef GRAPHTHEORY_DENSERGRAPH_H
#define GRAPHTHEORY_DENSERGRAPH_H

#include <iostream>
#include <vector>
#include <cassert>

using namespace std;

/**
 * 稠密图 --- 邻接矩阵实现
 *
 * 对平行边不存在，当存在边，则不更新边
 */
class DenserGraph {

private:
    int v, e;    //v --> 节点； e --> 边
    bool directed;    //是否是有向图
    vector<vector<bool>> g;  //临街矩阵（二维矩阵）

public:

    //构造函数：参数： 节点数， 是否有向
    DenserGraph(int v, bool directed) {
        this->v = v;
        e = 0;
        this->directed = directed;

        //初始化邻接矩阵
        for (int i = 0; i < v; i++) {
            g.push_back(vector<bool>(v, false));
        }
    }

    //未new空间，则不需要释放堆空间
    ~DenserGraph() {

    }

    int V() {
        return v;
    }

    int E() {
        return e;
    }

    //添加边，参数：需要连接的两个顶点的索引
    void addEdge(int a, int b) {

        assert(a >= 0 && a < v);
        assert(b >= 0 && b < v);


        //TODO 注意：当两个节点本来就有边则不添加该边,退出
        if (hasEdge(a, b)) {
            return;
        }

        g[a][b] = true;

        //无向图中添加边：对称性
        if (!directed) {
            g[b][a] = true;
        }
        e++;
    }

    //判断两节点是否存在边
    bool hasEdge(int a, int b) {
        assert(a >= 0 && a < v);
        assert(b >= 0 && b < v);

        return g[a][b];
    }

    void show() {
        //输出v个结点的临界顶点
        for (int i = 0; i < v; i++) {
            for (int j = 0; j < v; j++) {
                cout << g[i][j] << "\t";
            }
            cout << endl;
        }
    }

    class adjIterator {

    private:
        DenserGraph &G;  //需要遍历的图
        int v;     //遍历的节点
        int index; //遍历下标

    public:
        adjIterator(DenserGraph &graph, int v) : G(graph) {
            this->v = v;
            index = -1;
        }

        ~adjIterator() {

        }

        //开始
        int begin() {
            //清零下边
            index = -1;
            //寻找第一个为true的元素即为第一条边
            return next();
        }

        //下一个
        int next() {
            //遍历向量,寻找为TRUE的节点
            for (index += 1; index < G.V(); ++index) {
                if (G.g[v][index]) {
                    return index;
                }
            }
            return -1;
        }


        //是否结束
        bool end() {
            return index >= G.g[v].size();
        }
    };
};

#endif //GRAPHTHEORY_DENSERGRAPH_H
